package greedy.leetcode_502;

import java.util.PriorityQueue;

public class HeapSolution {
    /**
     * @param k       k个项目
     * @param W       资金
     * @param Profits 完成第 i 个项目可获得 P[i] 的利润
     * @param Capital 完成第 i 个项目所需要的花费 C[i]
     * @return
     */
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        /**
         * 利用小根堆，按花费升序排列，当 W >= 堆顶元素时，表示可以进行该项目。将所有可以进行的项目放入大根堆
         * 大根堆按照利润降序排列，每次都选择可获得最大利润的项目进行。
         */
        // 小根堆，存放<花费,利润>，按花费升序
        PriorityQueue<int[]> minCost = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        // 大根堆，存放<花费,利润>，按利润降序
        PriorityQueue<int[]> maxProfit = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
        for (int i = 0; i < Profits.length; i++) {
            minCost.offer(new int[]{Capital[i], Profits[i]});
        }
        for (int i = 0; i < k; i++) {
            // 资金可以进行项目，放入大根堆
            while (!minCost.isEmpty() && W >= minCost.peek()[0]) {
                maxProfit.offer(minCost.poll());
            }
            // 特殊情况：当资金不能启动任何项目时，直接返回
            if (maxProfit.isEmpty()) {
                return W;
            }
            W += maxProfit.poll()[1];
        }
        return W;
    }
}
